# -*- coding:utf-8 -*-
from __future__ import print_function
import sys
sys.path.append('../')
from tools import *

class Solution:
	# 返回合并后列表
	def Merge(self, pHead1, pHead2):
		# write code here
		if pHead1 == None:
			phead = pHead2
			return phead
		if pHead2 == None:
			phead = pHead1
			return phead
		if(pHead1.val > pHead2.val):
				phead = ListNode(pHead2.val)
				pHead2 = pHead2.next
		else:
			phead = ListNode(pHead1.val)
			pHead1 = pHead1.next
		temp = phead
		while True:
			if pHead1 == None:
				temp.next = pHead2
				return phead
			if pHead2 == None:
				temp.next = pHead1
				return phead
			if(pHead1.val > pHead2.val):
				temp.next = ListNode(pHead2.val)
				temp = temp.next
				pHead2 = pHead2.next
			else:
				temp.next = ListNode(pHead1.val)
				temp = temp.next
				pHead1 = pHead1.next